/*
 * @lc app=leetcode.cn id=710 lang=typescript
 *
 * [710] 黑名单中的随机数
 */

// @lc code=start
class Solution {
  map: Map<number, number> = new Map();
  black: Set<number> = new Set();
  bound: number;
  constructor(n: number, blacklist: number[]) {
    this.bound = n - blacklist.length;
    // 超过随机范围的黑名单
    for (const b of blacklist) {
      if (b >= this.bound) this.black.add(b);
    }

    let val = this.bound;
    // 超出随机范围数字跟黑名单数字做映射
    for (const b of blacklist) {
      if (b < this.bound) {
        while (this.black.has(val)) {
          val++;
        }
        this.map.set(b, val);
        val++;
      }
    }
  }

  pick(): number {
    const rand = Math.floor(Math.random() * this.bound);
    return this.map.get(rand) || rand;
  }
}

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(n, blacklist)
 * var param_1 = obj.pick()
 */
// @lc code=end
